package 数据结构.数组;

import java.util.Arrays;

/**
 * @author Veng Su 1344114844@qq.com
 * @date 2018/7/15 10:51
 */
public class Array <E>{
    private E[] data;
    private int size;

    /**
     * 构造函数，传入数组容量capacity构造一个数组
     *
     * @param capacity 数组容量
     */
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
    }
    public Array(E[] arr){
        data= (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i]=arr[i];
        }
    }

    /**
     * 无参构造函数，默认构造数组容量为10的数组
     */
    public Array() {
        data = (E[]) new Object[10];
    }

    /**
     * 获取元素中的元素个数
     *
     * @return Size 数组中的元素个数
     */
    public int getSize() {
        return size;
    }

    /**
     * 获取数组的容量
     *
     * @return 数组的容量capacity
     */
    public int getCapacity() {
        return data.length;
    }

    /**
     * 判断数组是否为空，即有没有元素
     *
     * @return 如果为空，返回true；否则返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 将动态数组转化为普通数组
     *
     * @return data 普通数组
     */
    public E[] toArray() {
        E[] res = (E[]) new Object[size];
        for (int i = 0; i < size; i++) {
            res[i] = data[i];
        }
        return res;
    }

    /**
     * 向数组头部插入元素
     *
     * @param element 元素
     */
    public void addFirst(E element) {
        add(0, element);
    }

    /**
     * 向数组末尾添加一个元素
     *
     * @param element 需要添加的元素
     */
    public void addLast(E element) {
        add(size, element);
    }

    /**
     * 向数组指定位置插入元素
     *
     * @param index   指定位置
     * @param element 元素
     */
    public void add(int index, E element) {
        if (size == data.length) {
            resize((int) (1.5*size));
        }
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("数组索引必须大于0，小于size的");
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = element;
        size++;
    }

    /**
     * 根据index返回值
     *
     * @param index 索引
     * @return 元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("参数错误 index: require <size&&>0");
        }
        return data[index];
    }

    public E getLast(){
        return get(size-1);
    }
    public E getFirst(){
        return get(0);
    }

    /**
     * 设置指定位置的元素
     *
     * @param index   索引
     * @param element 元素
     */
    public void set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("参数错误 index: require <size&&>0");
        }
        data[index] = element;
    }

    /**
     * 数组中是否包含某个元素
     *
     * @param element
     * @return 是，则包含；否，则不包含
     */
    public boolean contains(E element) {
        for (E e : data) {
            if (element .equals(e) ) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找数组中包含该元素的索引
     *
     * @param element 元素
     * @return 该元素的索引，如果不存在该元素，则返回-1
     */
    public int findOne(E element) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 从数组中查找某个元素，返回该元素的全部索引。没有则返回空
     *
     * @param element 要查找的元素
     * @return
     */
    public int[] findAll(E element) {
        Array<Integer> res = new Array();
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                res.addLast(i);
            }
        }
        if (res.isEmpty()) {
            return null;
        }

        return Arrays.stream(res.toArray())
                .mapToInt(Integer::valueOf)
                .toArray();
    }

    /**
     * 从数组中删除指定位置的元素，并返回删除的元素
     *
     * @param index 指定位置
     * @return int 删除的元素
     */
    public E remove(int index) {
        if (index >= size || index < 0) {
            throw new IllegalArgumentException("参数错误 index: require <size&&>0");
        }
        E res = data[index];
        for (int i = index; i < size-1; i++) {
            data[i] = data[i + 1];
        }
        size--;
        data[size]=null;//因为remove的时候最后一个还存在一个对象的应用所以要将引用置空，让jvm的垃圾回收器可以自动回收这个垃圾对象
        //注意：loitering object !=memory leak 游荡对象不等于内存泄漏
        lazyResize();
        return res;
    }

    /**
     * 根据索引删除多个元素
     * @param indexs 元素索引
     */
    public void removeAny(int[] indexs) {
        E[] cache = (E[]) new Object[size - indexs.length];
        int newSize = 0;
        for (int i = 0; i < indexs.length + 1; i++) {
            if (i == 0) {
                if (indexs[i] != 0) {
                    System.arraycopy(data, 0, cache, newSize, indexs[i]);
                    newSize = indexs[i];
                }
            } else if (i == indexs.length) {
                if (indexs[i - 1] < size - 1) {
                    System.arraycopy(data, indexs[i - 1] + 1, cache, newSize, data.length - indexs[i - 1] - 1);
                    newSize += data.length - indexs[i - 1] - 1;
                }
            } else {
                int length = indexs[i] - indexs[i - 1] - 1;
                System.arraycopy(data, indexs[i - 1] + 1, cache, newSize, length);
                newSize += length;
            }
        }
        size = newSize;
        data = cache;
        lazyResize();
    }

    /**
     * 从数组中删除第一个元素，并返回第一个元素
     *
     * @return 以前的第一个元素
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 从数组中删除最后一个元素，并返回最后一个元素
     *
     * @return 以前的最后一个元素
     */
    public E removeLast() {
        return remove(size - 1);
    }

    /**
     * 从数组中删除一个这个元素，有就删除，没有则不改变。有多个则删除一个
     *
     * @param element 要删除的元素
     * @return true 则移除成功，false则数组中没有该元素
     */
    public boolean removeOneElement(E element) {
        int index = findOne(element);
        if (index != -1) {
            remove(index);
            return true;
        }
        return false;
    }

    /**
     * 移除数组中所有是element的元素
     * @param element 元素
     * @return true 则移除成功，false则数组中没有该元素
     */
    public boolean removeAllElement(E element) {
        int[] indexs = findAll(element);
        if (indexs == null) {
            return false;
        }
        removeAny(indexs);
        return true;
    } 
    /**
     * 动态增加容量
     * @param newCapacity 新的容量
     */
    private void resize(int newCapacity){
        E[] newData= (E[]) new Object[newCapacity];
        System.arraycopy(data,0,newData,0,size);
        data=newData;
    }

    /**
     * 懒增加容量，保证有空闲的容量。
     */
    private  void lazyResize(){
        if (size==data.length/4&&data.length/2!=0)
            resize(data.length/2);
    }

    /**
     * 交换数组中两个元素的位置
     * @param i
     * @param j
     */
    public void swap(int i,int j){
        if (i<0||i>=size||j<0||j>=size){
            throw new IllegalArgumentException("索引错误，应该>0&&<=size");
        }
        E t=data[i];
        data[i]=data[j];
        data[j]=t;
    }

    /**
     * 设置打印格式，把size和capacity打印出来，以及data的元素
     *
     * @return String
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder(50);
        res.append(String.format("Array: size=%d,capasity=%d\n", size, data.length));
        res.append("[");
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i < size - 1) {
                res.append(",");
            }
        }
        res.append("]");
        return res.toString();
    }
}
